package com.example.leetcode.trietree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Trie {

    static class Node {
        Integer position;
        Character curChar;
        Map<Character, Integer> sons;
        Integer count = 0;
    }

    List<Node> tree = new ArrayList<>();

    Node curNode;
    Node root = new Node();

    public Trie() {
        root.position = 0;
        root.curChar = null;
        root.sons = new HashMap<>();
        curNode = root;
        tree.add(root);
    }

    public void insert(String word) {
        if (word == null || word.length() == 0) {
            return;
        }
        curNode = root;
        for (int i = 0; i < word.length(); i++) {
            Character c = word.charAt(i);
            Map<Character, Integer> sonNodes = curNode.sons;
            Integer sonPos = sonNodes.get(c);
            if (sonPos != null) {
                curNode = tree.get(sonPos);
            } else {
                Node sonNode = new Node();
                tree.add(sonNode);
                sonPos = tree.size() - 1;
                sonNode.position = sonPos;
                sonNode.curChar = c;
                sonNode.sons = new HashMap<>();
                sonNodes.put(c, sonPos);
                curNode = sonNode;
            }
        }
        curNode.count++;
    }

    public boolean search(String word) {
        return startsWith(word) && curNode.count > 0;
    }

    public boolean startsWith(String prefix) {
        if (prefix == null || prefix.length() == 0) {
            return true;
        }
        curNode = root;
        for (int i = 0; i < prefix.length(); i++) {
            Character c = prefix.charAt(i);
            Map<Character, Integer> sonNodes = curNode.sons;
            Integer sonPos = sonNodes.get(c);
            if (sonPos == null) {
                return false;
            } else {
                curNode = tree.get(sonPos);
            }
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

public class leetcode208 {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        System.out.println(trie.search("apple"));   // 返回 True
        System.out.println(trie.search("app"));     // 返回 False
        System.out.println(trie.startsWith("app")); // 返回 True
        trie.insert("app");
        System.out.println(trie.search("app"));     // 返回 True
    }
}
